package lc.q150_200;

public class Q152 {
    public int maxProduct(int[] nums) {
        // 使用一个二维数组表示i,j直接所有数的乘积
        // 首先对接线的值都是等于本身
        // 然后使用dp算法根据公式计算
        // 因为不需要记住所有的值，可以只需要记住上一个值就行
        // 继续优化，包含i的前缀最优解一定是Integer.max(i, i * per(i-1)),那么只需要记住前一个最优解就行
        int maxF = nums[0];
        int minF = nums[0];
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int mx =maxF;
            int my = minF;
            maxF = Integer.max(nums[i], Integer.max(nums[i] * mx, nums[i] * my));
            minF = Integer.min(nums[i], Integer.min(nums[i] * mx, nums[i] * my));
            ans = Integer.max(ans, maxF);
        }
        return ans;
    }

    public static void main(String[] args) {
        Q152 q152 = new Q152();
        int i = q152.maxProduct(new int[]{5,2, 3, -2,-10, 4,3});
        System.out.println(i);
    }
}
